/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM76 正则表达式匹配
 * https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4?tpId=295&tqId=1375406&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 * User: DELL
 * Data: 2022-11-21
 * Time: 22:58
 */

//动态规划经典题  较难
//详细解析见牛客网
import java.util.*;

public class Solution {
    public boolean match (String str, String pattern) {
        int len1 = str.length();
        int len2 = pattern.length();
        //dp[i][j]表示的是str的前i个字符和pattern的前j个字符是否可以匹配
        boolean[][] dp = new boolean[len1+1][len2+1];
        //初始化第一行
        //当两个串都为空的时候，可以匹配
        dp[0][0] = true;
        dp[0][1] = false;
        for (int i = 2; i < len2 + 1; i++) {
            if (pattern.charAt(i-1) == '*') {
                dp[0][i] = dp[0][i-2];
            }
        }
        //进行状态转移
        for (int i = 1; i < len1 + 1; i++) {
            for (int j = 1; j < len2 + 1; j++) {
                int ch = pattern.charAt(j-1);
                //直接可以匹配的情况
                if (ch == '.' || ch == str.charAt(i-1)) {
                    dp[i][j] = dp[i-1][j-1];
                }
                //遇见‘*’的情况
                if (j >=2 && ch == '*') {
                    //'*'前的字符符合多出现一次和只出现一次的情况
                    int pre = pattern.charAt(j-2);
                    if (pre == '.' || pre == str.charAt(i-1)) {
                        dp[i][j] = dp[i-1][j] || dp[i-1][j-2] || dp[i][j-2];
                    } else { //以上情况不符合的话，只有让前面的字符出现0次
                        dp[i][j] = dp[i][j-2];
                    }
                }
            }
        }
        return dp[len1][len2];
    }
}